#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll N = 1e3 + 10;
ll a[N][N];
ll n, m;
ll mp[N][N];
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
ll ans = 1111111;
void dfs(ll k, ll res) // 第k位同学，res个考场
{

    if (ans <= res)
    {
        return;
    }
    if (k == n + 1)
    {
        ans = min(ans, res);
        return;
    }
    for (ll i = 1; i <= res; i++) // 依次遍历每个考场，看有没有认识他的
    {
        ll u = 1;
        while (mp[i][u] && !a[k][mp[i][u]]) // 如果第i个考场的第u名同学存在且不认识，继续往后遍历
        {
            u++;
        }
        // 注意这个u如果每个人都不认识的话，这个u代表的是本考场人数加一
        // 那么这个考场就没有第u个人,
        if (!mp[i][u]) // 没有第u个，让第k个同学成为第u个
        {
            mp[i][u] = k;
            dfs(k + 1, res);
            mp[i][u] = 0;
        }
    }
    mp[res + 1][1] = k;
    dfs(k + 1, res + 1);
    mp[res + 1][1] = 0;
}
void solve()
{

    cin >> n >> m;
    for (ll i = 1; i <= m; i++)
    {
        ll aa, bb;
        cin >> aa >> bb;
        a[aa][bb] = 1;
        a[bb][aa] = 1;
    }
    dfs(1, 0); // 第一位同学0个考场
    cout << ans;
}
int main()
{
    ll t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}